package recursion


func GetNQueenAns(n int) int{
	return NQueueProcess(n, 0, make([]int, n))
}

func NQueueProcess(n int, row int, record []int) int {
	if row == n {return 1}
	res := 0
	for col:=0; col<n; col++ {
		if IsValid(row, col, record){
			record[row] = col
			res += NQueueProcess(n, row+1, record)
		}
	}
	return res
}

func IsValid(row, col int, record []int) bool {
	for i:=0; i<row; i++ {
		if col == record[i] || abs(row-i) == abs(record[i] - col) {
			return false
		}
	}
	return true
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func GetNQueenAns2(n int) int {
	limit := 0
	for i:=0; i<n; i++ {
		limit += 1 << i
	}
	return GetNQueenAns2Process(limit, 0, 0, 0)
}

func GetNQueenAns2Process(limit int, colLimit, leftDiaLim, rightDiaLim int) int {
	if colLimit == limit {
		return 1
	}
	can := ^(colLimit | leftDiaLim | rightDiaLim) & limit
	var ans int
	for can != 0 {
		rightOne := can & (^can + 1)
		can -= rightOne
		ans += GetNQueenAns2Process(
			limit,
			rightOne | colLimit,
			(leftDiaLim | rightOne) << 1,
			(rightDiaLim | rightOne) >> 1,
		)
	}
	return ans
}